from functools import cache


class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        num = list(map(int, str(n)))

        @cache
        def f(id, limit, used):
            if id == len(num):
                return int(used > 1)
            r = num[id] if limit else 9
            ans = 0
            for i in range(r + 1):
                if used >> i & 1 == 0:
                    ans += f(
                        id + 1,
                        limit and i == r,
                        used ^ (1 << i) if i > 0 or used > 1 else used,
                    )
            return ans

        return f(0, True, 0)


c = [20, 5, 135]
s = Solution()
for i in c:
    print(s.countSpecialNumbers(i))
